package com.ywk.base.dataStructure.sort;

import java.text.SimpleDateFormat;
import java.util.Date;
//桶排序：金典的空间换时间的方式（占用内存大：每个桶的容量都是待排序数组的数量）
public class RadixSort {

	public static void main(String[] args) {
		//int[] nums = { 53, 3, 542, 748, 14, 214 };
		int[] nums = new int[8000000];
		for (int i = 0; i < nums.length; i++) {
			nums[i] = (int) (Math.random() * 80000);
		}
		Date d1 = new Date();
		SimpleDateFormat s = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");// 日期格式
		System.out.println("排序前的时间：" + s.format(d1));
		radixSort(nums);
		Date d2 = new Date();
		System.out.println("排序后的时间：" + s.format(d2));
		//System.out.println(Arrays.toString(nums));
	}

	public static void radixSort(int[] nums) {
		int[][] bucket = new int[10][nums.length];
		int[] bucketElementCount = new int[10];
		//第一次取个位，第二次取十位
		for (int i = 0; i < maxDigit(nums); i++) {
			//取出对应的位数（个、十、百...）
			for (int j = 0; j < nums.length; j++) {
				
				int digitOfElement = (int) (nums[j] / Math.pow(10, i)%10);
				bucket[digitOfElement][bucketElementCount[digitOfElement]] = nums[j];
				bucketElementCount[digitOfElement]++;
			}
			int numIndex=-1;
			//每个桶中元素个数
			for (int l = 0; l < bucketElementCount.length; l++) {
				if(bucketElementCount[l]!=0) {
					for (int j = 0; j < bucketElementCount[l]; j++) {
						numIndex++;
						nums[numIndex]=bucket[l][j];
					}
					bucketElementCount[l]=0;//重置数组
				}
				
			}
			
		}
		
	}

	public static int maxDigit(int[] nums) {
		int maxOfDigit = 0;
		int max = nums[0];
		for (int i = 1; i < nums.length - 1; i++) {
			if (max < nums[i]) {
				max = nums[i];
			}
		}
		maxOfDigit = (max + "").length();
		return maxOfDigit;
	}
}
